package org.liaohailong.helloworld.practice;

import java.util.Random;

/**
 * Author: liaohailong
 * Time: 2021/6/21 14:19
 * Describe: 设计问题
 */
public class DesignPractice {


    /**
     * LC 打乱数组
     */
    public static final class Solution {
        private final int[] nums;
        private final Random random = new Random();

        public Solution(int[] nums) {
            this.nums = nums;
        }

        /**
         * Resets the array to its original configuration and return it.
         */
        public int[] reset() {
            return nums;
        }

        /**
         * Returns a random shuffling of the array.
         */
        public int[] shuffle() {
            int[] clone = nums.clone();
            for (int i = 0; i < clone.length; i++) {
                int j = i + random.nextInt(clone.length - i);
                swap(clone, i, j);
            }
            return clone;
        }

        private void swap(int[] arr, int i, int j) {
            if (i != j) {
                arr[i] ^= arr[j];
                arr[j] ^= arr[i];
                arr[i] ^= arr[j];
            }
        }
    }

    /**
     * LC 最小栈
     */
    public static final class MinStack {
        private ListNode foot = null;

        /**
         * initialize your data structure here.
         */
        public MinStack() {

        }

        public void push(int val) {
            if (foot == null) {
                foot = new ListNode(val, val);
            } else {
                ListNode temp = foot;
                foot = new ListNode(val, Math.min(temp.min, val));
                foot.prev = temp;
            }
        }

        public void pop() {
            foot = foot.prev;
        }

        public int top() {
            return foot.val;
        }

        public int getMin() {
            return foot.min;
        }

        private static final class ListNode {
            final int val;
            final int min;
            ListNode prev;

            public ListNode(int val, int min) {
                this.val = val;
                this.min = min;
            }
        }
    }

    public int sum(int[] arr) {
        return _sum(arr, 0, arr.length - 1);
    }

    private int _sum(int[] arr, int i, int j) {
        if (i == j) return arr[i];
        else return arr[i] + _sum(arr, i + 1, j);
    }
}
